function BinarySearchTree() {

    // 封装节点
    function Node(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }

    // 属性
    this.root = null;

    // 这是对外暴露的方法
    BinarySearchTree.prototype.insert = function (key) {

        // 建立新节点
        var newNode = new Node(key);

        // 判断root根节点是否存在
        if (this.root == null) {
            this.root = newNode;
        } else {
            // 这里采用递归
            this.insertNode(this.root, newNode);
        }
    }

    // 这是内部使用的方法
    BinarySearchTree.prototype.insertNode = function (node, newNode) {

        // 开始比较大小
        if (newNode.key < node.key) { // 从左边开始找
            // 先判断，如果为空，直接插入
            if (node.left == null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else { // 从右边找
            if (node.right == null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }


    // 先序遍历
    BinarySearchTree.prototype.preOrderTraversal = function (handler) {
        this.preOrderTraversalNode(this.root, handler)
    }

    // 先序内部调用方法
    BinarySearchTree.prototype.preOrderTraversalNode = function (node, handler) {

        if (node != null) {
            // handler是用来封装打印的回调函数
            handler(node.key);

            // 从左子树开始找
            this.preOrderTraversalNode(node.left, handler);

            // 从右子树找
            this.preOrderTraversalNode(node.right, handler);
        }
    }

    // 中序遍历
    BinarySearchTree.prototype.midOrderTraversal = function (handler) {
        this.midOrderTraversalNode(this.root, handler)
    }

    // 中序内部调用方法
    BinarySearchTree.prototype.midOrderTraversalNode = function (node, handler) {

        if (node != null) {

            // 从左子树开始找
            this.midOrderTraversalNode(node.left, handler);

            // handler是用来封装打印的回调函数
            handler(node.key);

            // 从右子树找
            this.midOrderTraversalNode(node.right, handler);
        }
    }


    // 后序遍历
    BinarySearchTree.prototype.postOrderTraversal = function (handler) {
        this.postOrderTraversalNode(this.root, handler)
    }

    // 后序内部调用方法
    BinarySearchTree.prototype.postOrderTraversalNode = function (node, handler) {

        if (node != null) {

            // 从左子树开始找
            this.postOrderTraversalNode(node.left, handler);

            // 从右子树找
            this.postOrderTraversalNode(node.right, handler);

            // handler是用来封装打印的回调函数
            handler(node.key);
        }
    }


    // max方法
    BinarySearchTree.prototype.max = function () {
        var node = this.root;

        while(node != null && node.right != null) {
            node = node.right
        }

        return node.key
    }

    // min方法
    BinarySearchTree.prototype.min = function () {
        var node = this.root;

        while(node != null && node.left != null) {
            node = node.left
        }

        return node.key
    }

    // search暴露对外的方法
    BinarySearchTree.prototype.search = function (key) {
        return this.searchNode(this.root, key);
    }

    // search方法 递归来做
    BinarySearchTree.prototype.searchNode = function (node, key) {
        // node不为空，开始搜寻
        if (node != null) {
            if (key < node.key) { //去左边找

                // 在最里面的递归函数返回一个boolean值后，这个函数接下来也没啥要执行的了，直接返回。
                return this.searchNode(node.left, key);
            } else if (key > node.key) { //去右边找

                return this.searchNode(node.right, key);
            } else {
                return true;
            }
        } else {
            // 都到null了还没找到
            return false;
        }
    }


    // remove方法
    BinarySearchTree.prototype.remove = function (key) {

        // 先查找到这个key，这三个变量是删除时所必须的
        var current = this.root;
        var parent = null;
        var isLeft = true;

        while (current.key != key) {
            parent = current;
            // 进行判断
            if (key < current.key) {
                current = current.left;
                isLeft = true;
            } else {
                current = current.right;
                isLeft = false;
            }

            // 查到空都没有找到
            if (current == null) {
                return false;
            }
        }

        // 删除的节点是叶子节点
        if (current.left == null && current.right == null) {
            // 删除的节点是叶子节点同时也是根节点
            if (current == this.root) {
                this.root = null;
            } else if (isLeft) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else if (current.right == null) { // 删除的节点只有一个左子节点
            // 这个节点是根节点
            if (current == this.root) {
                this.root = current.left;
            } else if (isLeft) { // 这个节点是左节点
                parent.left = current.left;
            } else { // 这个节点是右节点
                parent.right = current.left;
            }
        } else if (current.left == null) { //删除的节点只有一个右子节点
            // 这个节点是根节点
            if (current == this.root) {
                this.root = current.right;
            } else if (isLeft) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        } else { // 删除的节点有两个子节点

            // 获得后继节点
            var successor = this.getSuccessor(current);

            // 如果是根节点
            if (current == this.root) {
                successor.left = current.left;
                successor.right = current.right;
                this.root = successor;
            } else if (isLeft) { // 删除的有两个子节点的节点是它父节点的左
                successor.left = current.left;
                successor.right = current.right;
                parent.left = successor;
            } else { // 删除的有两个子节点的节点是它父节点的右
                successor.left = current.left;
                successor.right = current.right;
                parent.right = successor;
            }

        }

    }


    // 寻找后继的方法
    BinarySearchTree.prototype.getSuccessor = function (delNode) {

        var current = delNode.right;
        var successor = delNode;
        var successorParent = delNode;
        // 还需要一个 后继节点的父，因为需要把和后继节点这根线断了

        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }

        // 把后继节点的父和后继节点那根线断了
        successorParent.left = successor.right;

        // 这个就是后继节点
        return successor;
    }
}